package com.algorithm.basic;
/*
 *@Author:DOWN
 *@Date:2022/01/11 15:31
 *@Comment:插入排序 每一次循环 从指定的 头尾index 一一比较大小 修改元素位置
 */
import com.algorithm.testutils.ArrayGenerator;
import com.algorithm.testutils.SortingHelp;

public class InsertionSort {
    public static <E extends Comparable<E>> void sort(E[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找元素 arr[i] 合适的插入位置
           for( int j = i ; j > 0 ; j -- ) {
               if( arr[j].compareTo( arr[j-1] ) < 0 ) {
                   swap( arr, j , j-1 );
               } else {
                   break;
               }
           }
        }
    }
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) throws Exception {
        Integer[] arr =  ArrayGenerator.getRandomArrays(10,100000000);
        SortingHelp.sortTest("com.algorithm.yyy.InsertionSort","sort",arr);
    }

}